/*
* 2010
* Authors: Dmitry Kolyanov <dk90.spb@gmail.com>, Ksenyia Cypan <ksenyiacypan@gmail.com>
*/

#include "stdafx.h"

maxcut::maxcut()
{
	maxcut_size = 0;
}

maxcut::~maxcut()
{
}

w_size_type maxcut::get_maxcut_size()
{
	return maxcut_size;
}

void maxcut::make_even_number_of_vertices(Graph &g)
{
	size_t num_v = num_vertices(g);

	if(num_v % 2 != 0)
		even_vertices_num = num_v+1;
	else
		even_vertices_num = num_v;
}

void maxcut::create_matchings(const Graph &g, Matchings &matchings)
{
	graph_traits<Graph>::edge_iterator e1, e1_end;

	for(tie(e1 ,e1_end) = edges(g); e1 != e1_end; ++e1)
	{
		matchings[number_of_matching(*e1, g)].second += get(edge_weight, g, *e1);
		matchings[number_of_matching(*e1, g)].first->push_back(*e1);
	}
}

void maxcut::fill_max_matching(Edge_set &es, Matchings &matchings)
{
	w_size_type max_matching_num = 0;
	graph_traits<Graph>::edge_iterator e1, e1_end;

	for(Matchings::iterator wi = matchings.begin(); wi != matchings.end(); ++wi)
	{
		if(max_matching_num < wi->second)
		{
			es = *wi->first;
			max_matching_num = wi->second;
		}
	}

	for(Matchings::iterator wi = matchings.begin(); wi != matchings.end(); ++wi)
		delete wi->first;
	matchings.clear();
}

bool maxcut::is_black(Vertex v, const Graph &g)
{
	return get(vertex_color, g, v) == maxcut_t::black;
}

bool maxcut::is_gray(Vertex v, const Graph &g)
{
	return get(vertex_color, g, v) == maxcut_t::gray;
}

bool maxcut::is_white(Vertex v, const Graph &g)
{
	return get(vertex_color, g, v) == maxcut_t::white;
}

bool maxcut::is_varigated(Edge e, const Graph &g)
{
	return get(vertex_color, g, source(e,g)) + get(vertex_color, g, target(e,g)) == maxcut_t::white + maxcut_t::black;
}

void maxcut::variegated_out_edges(const Vertex v, Edge_set &var_out_edges, const Graph &g)
{
	graph_traits<Graph>::out_edge_iterator e1, e1_end; 
	for(tie(e1 ,e1_end) = out_edges(v,g); e1 != e1_end; ++e1)
	{
		if(is_varigated(*e1, g))
			var_out_edges.push_back(*e1);
	}
}

void maxcut::variegated_out_edges(Edge e, Edge_set &var_out_edges, const Graph &g)
{
	variegated_out_edges(target(e,g), var_out_edges, g);
	variegated_out_edges(source(e,g), var_out_edges, g);
}

w_size_type maxcut::varigated_size(Vertex u, Vertex v, Edge e, Graph &g)
{
	Edge_set es;
	paint_edge(u, v, g);
	variegated_out_edges(e, es, g);
	return edge_set_size(es, g);
}

w_size_type maxcut::varigated_size(Vertex u, int color, Graph &g)
{
	Edge_set es;
	put(vertex_color, g, u, color);
	variegated_out_edges(u, es, g);
	return edge_set_size(es, g);
}

void maxcut::create_vertex_mapping(const Graph &g)
{
	graph_traits<Graph>::vertex_iterator v, v_end;
	for(tie(v, v_end) = vertices(g); v != v_end; ++v)
		vertices_numbers[*v] = std::distance(v, v_end);
}

int maxcut::number_of_matching(Edge e, const Graph &g)
{
	size_t matchings_number = even_vertices_num - 1;

	size_t u = vertices_numbers[source(e,g)];
	size_t v = vertices_numbers[target(e,g)];

	if(u == matchings_number)
		return (v * 2) % (matchings_number);
	if(v == matchings_number)
		return (u * 2) % (matchings_number);
	else
		return (v + u) % (matchings_number);
}

w_size_type maxcut::edge_set_size(const Edge_set &es, const Graph &g)
{
	w_size_type size = 0;

	for(Edge_set::const_iterator ei = es.begin(); ei != es.end(); ++ei)
		size += get(edge_weight, g, *ei);

	return size;
}

void maxcut::create_gray_set(Vertex_set &gray_set, const Graph &g)
{
	graph_traits<Graph>::vertex_iterator v, v_end;

	for(tie(v, v_end) = vertices(g); v != v_end; ++v)
	{
		if(is_gray(*v, g))
			gray_set.push_back(*v);
	}
}

void maxcut::paint_edge(Vertex u, Vertex v, Graph &g){
	paint_black(v, g);
	paint_white(u, g);
}

void maxcut::paint_black(Vertex v, Graph &g){
	put(vertex_color, g, v, maxcut_t::black);
}

void maxcut::paint_white(Vertex v, Graph &g){
	put(vertex_color, g, v, maxcut_t::white);
}

void maxcut::paint_gray(Vertex v, Graph &g){
	put(vertex_color, g, v, maxcut_t::gray);
}

void maxcut::prepare_to_start(Graph &g, Matchings &matchings)
{
	make_even_number_of_vertices(g);

	graph_traits<Graph>::vertex_iterator v, v_end;
	for(tie(v, v_end) = vertices(g); v != v_end; ++v)
		paint_gray(*v, g);

	if(num_vertices(g) > 0)
	{
		for(size_t i = 0; i < even_vertices_num; i++)
			matchings.push_back(Matching(new Edge_set(), 0));
	}

	create_vertex_mapping(g);
}

void maxcut::combinatorial_algorithm(Graph &g)
{
	Matchings matchings;
	prepare_to_start(g, matchings);
	create_matchings(g, matchings);

	Edge_set max_matching;
	fill_max_matching(max_matching, matchings);

	for(Edge_set::iterator ei = max_matching.begin(); ei != max_matching.end(); ++ei)
	{
		Vertex u = source(*ei, g);
		Vertex v = target(*ei, g);
		if(varigated_size(u, v, *ei, g) > varigated_size(v, u, *ei, g))
			paint_edge(u, v, g);
	}

	Vertex_set gray_set;
	create_gray_set(gray_set, g);

	for(Vertex_set::iterator vi = gray_set.begin(); vi != gray_set.end(); ++vi)
	{
		if(varigated_size(*vi, maxcut_t::black, g) > varigated_size(*vi, maxcut_t::white, g))
			paint_black(*vi, g);
	}

	graph_traits<Graph>::edge_iterator e1, e1_end;
	for(tie(e1 ,e1_end) = edges(g); e1 != e1_end; ++e1)
	{
		if(is_varigated(*e1, g))
			maxcut_size += get(edge_weight, g, *e1);
	}
}